#include <vector>

using std::vector;

/**
 * private utility function used to detect if we have finished covering
 * @return	true if the first n elements of the array are all 1
 */
bool finished(int *array, size_t n) 
{
    int *end = array + n;
    while ( array != end) {
	if (*array++ != 1) { return false; }
    }
    return true;
}

/**
 * Initialize the row and/or column sum arrays with the given matrix.
 * Modifies
 *
 * @param   matrix	binary
 * @param   rowsums	int[] of row sums, NULL if not needed
 * @param   colsums	int[] of column sums, NULL if not needed
 */
void initialize_row_column_sums (
	vector<vector<int> > &matrix,
	int *rowsums,
	int *colsums
	)
{
    if (rowsums == NULL && colsums == NULL ) return ;
    size_t ncols = matrix.front().size();

    // initialize colsums to all 0's
    // not needed for rowsums b/c rowsum is assigned directly,
    // whereas colsum is incremented
    if (colsums != NULL) {
	for (int i=0; i < ncols; ++i) { colsums[i] = 0;}
    }

    /* initialize rowsums: count the 1's in each row;  at the same time,
     * initialize colsums: count the 1's in each column */
    int *row = rowsums;
    vector<vector<int> >::iterator rowvi = matrix.begin();
    vector<vector<int> >::iterator rowendi = matrix.end();
    while (rowvi != rowendi) {
	int rowcount = 0;
	int endcol = rowvi->size();
	for (int j = 0; j< endcol; j++) {
	    int bit = rowvi->at(j);
	    rowcount += bit;
	    if (colsums != NULL) {
		colsums[j] += bit;
	    }
	}
	if ( rowsums != NULL ) {
	    *row = rowcount;
	    ++row;
	}
	++rowvi;
    }
}

/**
 * Cover matrix with a row, i.e. mark every column in the row as covered
 * and also remove the row and all covered columns from the matrix.
 * Deleting a '1' at [i][j] detaches vertex i from column j. Doing this to
 * a row has the effect of removing the vertex, and doing it to a column
 * has the effect of removing the segment.
 * Ensures that rowsums and colsums are updated if they are not NULL.
 * Modifies: matrix, cover, rowsums, colsums
 *
 * Algorithm description:
 * . for each column with a 1 in the row
 * . mark column as covered (in cover array)
 * . delete all 1's in the column (change it to 0)
 * . update row & column counts as needed
 *
 * @param   matrix	matrix to cover
 * @param   rowi	index of row to use
 * @param   cover	int array of whether column is covered (1 = covered)
 * @param   rowsums	int array of rowsums, set to NULL if not needed
 * @param   colsums	int array of colsums, set to NULL if not needed
 */
void cover_with_row (
	vector< vector<int> > &matrix,
	size_t rowi,
	int *cover,
	int *rowsums,
	int *colsums
    )
{
    vector<int> &rowv = matrix.at(rowi);// get the row vector to cover with
    int endcol = rowv.size();
    for (int j = 0; j < endcol; j++) {	// for all columns j
	if (rowv.at(j) == 1) {		// if the rowv has a 1 in column j
	    cover[j] = 1;		// mark column j as covered

	    /* remove 1's from covered column */
	    int endrow = matrix.size();
	    for (int i=0; i<endrow; i++) {		// for all rows i
		if (matrix.at(i).at(j) == 1) {  // if element [i,j] is a 1
		    matrix.at(i).at(j) = 0;	// set it to 0 and ...
		    // decrement counts for row i and/or column j
		    if (rowsums != NULL) { --rowsums[i]; }
		    if (colsums != NULL) { --colsums[j]; }
		}
	    }
	}
    }
}

